package com.zhang.sort.cmp;

import com.zhang.sort.Sort;

import java.util.*;

/**
 * @author ZhangJiXin
 * @Description 希尔排序也被称为递减增量排序
 * @date 2021/4/22 18:42
 */
public class ShellSort<E> extends Sort<E> {
    /**
     * 希尔排序把序列看作是一个矩阵,分成m列,逐列进行排序
     *  m从某个整数逐渐减为1
     *  当m为1时,整个序列将完全有序
     * 矩阵的列数取决于 步长序列
     *  比如,如果步长序列为{1,5,19,41,109},就代表依次分成109列、41列、19列、5列、1列进行排序
     *  不同的步长序列,执行效率也不同
     */
    @Override
    protected void sort() {
        Queue<Integer> queue = robertSedgewickStepSequence();
        while (!queue.isEmpty()) {
            Integer poll = queue.poll();
            sort(poll);
        }
    }


    private void sort(int step) {
        for (int col = 0; col < step; col++) {
            for (int i = col + step; i < array.length; i += step) {
                int cur = i;
                while (cur > col && cmp(cur, cur - step) < 0) {
                    swap(cur, cur - step);
                    cur -= step;
                }
            }
        }
    }

    /**
     * 希尔步长序列
     *
     * @return 返回存储的步长序列的双端队列
     */
    private Deque<Integer> shellStepSequence() {
        Deque<Integer> deque = new LinkedList<>();
        int length = array.length;
        while ((length = length >> 1) > 0) {
            deque.offer(length);
        }
        return deque;
    }

    /**
     * 罗伯特·塞奇威克发明的步长序列
     * @return 返回存储的步长序列的双端队列
     */
    private Deque<Integer> robertSedgewickStepSequence() {
        Deque<Integer> deque = new LinkedList<>();
        int k = 0, step = 0;
        while (true) {
            if (k % 2 == 0) {
                int pow = (int) Math.pow(2, k >> 1);
                step = 1 + 9 * (pow * pow - pow);
            } else {
                int pow1 = (int) Math.pow(2, (k - 1) >> 1);
                int pow2 = (int) Math.pow(2, (k + 1) >> 1);
                step = 1 + 8 * pow1 * pow2 - 6 * pow2;
            }
            if (step >= array.length) {
                break;
            }
            deque.push(step);
            k++;
        }
        return deque;
    }
}
